package day2_linkedlist.mylink;

/**
 * 不带头的单链表实现
 */

class Node {
    int val;
    Node next;

    public Node(int val) {
        this.val = val;
    }

    public Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }
}

public class SingleLinkedList {
    private int size;
    private Node head;

    public void addFirst(int data) {
        // 产生新结点
        Node node = new Node(data);
        if (head != null) {
            node.next = head;
        }
        head = node;
        size ++;
    }

    public void addIndex(int index,int data) {
        if (index < 0 || index > size) {
            System.err.println("add index illegal!");
            return;
        }
        if (size == 0) {
            addFirst(data);
            return;
        }
        // 产生新节点
        Node node = new Node(data);
        Node prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        // 此时prev指向待插入结点的前驱
        node.next = prev.next;
        prev.next = node;
        size ++;
    }

    public void addLast(int data) {
        addIndex(size,data);
    }

    public int get(int index) {
        if (rangeCheck(index)) {
            Node cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            return cur.val;
        }else {
            System.err.println("get index illegal!");
            return -1;
        }
    }

    public int set(int index,int value) {
        if (rangeCheck(index)) {
            Node cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            int oldVal = cur.val;
            cur.val = value;
            return oldVal;
        }else {
            System.err.println("set index illegal!");
            return -1;
        }
    }

    public void removeIndex(int index) {
        if (rangeCheck(index)) {
            if (index == 0) {
                Node cur = head;
                head = head.next;
                cur.next = null;
                size --;
                return;
            }
            Node prev = head;
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
            // 此时prev是待删除结点的前驱
            Node cur = prev.next;
            prev.next = cur.next;
            cur.next = null;
            size --;
        }else {
            System.err.println("remove index illegal!");
        }
    }

    public void removeValueOnce(int value) {
        // 先处理头结点的情况
        if (head.val == value) {
            Node node = head;
            head = head.next;
            size --;
            node.next = null;
            return;
        }
        // 再处理后续结点情况
        Node prev = head;
        while (prev.next != null) {
            if (prev.next.val == value) {
                // 此时prev是待删除结点的前驱
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size --;
                break;
            }
            prev = prev.next;
        }
    }

    public void removeAllValue(int value) {
        // 如果头结点恰好是待删除的结点
        while (head != null && head.val == value) {
            Node node = head;
            head = head.next;
            size --;
            node.next = null;
        }
        // 此时head一定不是待删除的结点
        Node prev = head;
        while (prev.next != null) {
            // 此时prev恰好是待删除的结点
            if (prev.next.val == value) {
                Node cur = prev.next;
                prev.next = cur.next;
                size --;
                // 删除完当前结点后，prev指针不动
                // 继续判断下一个结点是否为待删除的结点
                cur.next = null;
            }else {
                prev = prev.next;
            }
        }
    }



    private boolean rangeCheck(int index) {
        if (index < 0 || index >= size) {
            return false;
        }else {
            return true;
        }
    }

    @Override
    public String toString() {
        String ret = "";
        Node cur = head;
        while (cur != null) {
            ret += cur.val + "->";
            cur = cur.next;
        }
        ret += "NULL";
        return ret;
    }

    /**
     * 递归实现链表的添加
     * @param index
     * @param val
     */
    public void addIndexR(int index,int val) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add index illegal");
        }
        this.head = addIndexInternal(head,index,val);
    }

    /**
     * 在以当前head为头结点的链表中的index位置插入新的元素val
     * @param head
     * @param index
     * @param val
     * @return
     */
    private Node addIndexInternal(Node head, int index, int val) {
        // 1.base case
        if (index == 0) {
            Node node = new Node(val);
            node.next = head;
            head = node;
            size ++;
            return node;
        }
        head.next = addIndexInternal(head.next,index - 1,val);
        return head;
    }

    /**
     * 递归顺序输出单链表节点
     * @param node 当前节点
     */
    public void print(Node node) {
        if (node == null) {
            return;
        }
        // 前序位置
        System.out.print(node.val + "->");
        if (node.next == null) {
            System.out.print("NULL\n");
        }
        print(node.next);
    }
    /**
     * 递归方式逆置输出单链表节点
     * @param head
     */
    int count = 0;
    public void printReverse(Node head) {
        if (head == null) {
            return;
        }
        // 前序位置,给每个节点编号
        count ++;
        printReverse(head.next);
        // 后序位置
        System.out.print(head.val + "->");
        // 每当倒序输出一个节点值，count--
        count --;
        if (count == 0) {
            System.out.print("NULL");
        }
    }
    public int getSize() {
        return size;
    }

    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addLast(3);
        singleLinkedList.addLast(3);
        singleLinkedList.addLast(2);
        singleLinkedList.addLast(1);
        singleLinkedList.addFirst(3);
        // 3 3 3 2 1
        singleLinkedList.print(singleLinkedList.head);
        System.out.println("=====================");
        singleLinkedList.printReverse(singleLinkedList.head);
    }
}
